<?php
/**
 * @author : lihui
 * @email  : lihui@mama.com
 * @time   : 2022/11/11 16:49
 * 最大堆测试用例
 */

namespace Xxb\XxbPhpAlgo\TestCase;

use Xxb\XxbPhpAlgo\MaxHeap;

class MaxHeapTest
{
    /**
     * @var MaxHeap
     */
    private $heap;

    public function __construct()
    {
        $this->heap = new MaxHeap();
    }

    /**
     * 验证最大堆的push
     * @param int $total
     *
     * @return bool
     */
    public function testPush($total = 100000)
    {
        for ($i=0; $i < $total; $i++) {
            $this->heap->push(mt_rand(0, PHP_INT_MAX));
        }

        return $this->verifyHeap($total);
    }

    /**
     * 验证数组堆化
     * @param int $n
     *
     * @return false
     */
    public function testHeapify($n = 100)
    {
        $arr = [];
        for ($i=0; $i<$n; $i++) {
            array_push($arr, mt_rand(0, pow($n, 2)));
        }

        $this->heap->heapify($arr);

        return $this->verifyHeap($n);
    }

    /**
     * 验证最大堆是否合法：
     * 1. 依次取出最大值
     * 2. 比较取出的最大值是否满足从大到小
     * @param $total
     *
     * @return bool
     */
    private function verifyHeap($total)
    {
        $result = [];

        for ($i=0; $i < $total; $i++) {
            $result[] = $this->heap->extractMax();
        }

        // 验证
        for ($i=1; $i < $total; $i++) {
            if ($result[$i-1] < $result[$i]) {
                return false;
            }
        }

        echo implode(',', $result) . PHP_EOL;

        return true;
    }
}
